// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-17 13:51
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.ACWing.DataTrains.DigitTriangle;

import java.util.Arrays;
import java.util.Scanner;

public class digitTriangle {
    /*
        数字三角形
        状态设计: f[i][j]:第i行第j列位置上的最大路径和
        状态初始化： 每一个位置的初始化状态为0，起点的初始化为其值
        状态转移：每一个位置的前驱节点可能有两个，取最大的作为最大路径和
        结果输出: 最后一行的中最大的路径和就是结果，可以在状态转移的过程中，使用max表示整个数字三角形的最大路径和
     */
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int layer = myScanner.nextInt();
        // 因为第i行有i个数据，所以使用动态数组表示
        /*-----数据初始化-----*/
        int[][] data = new int[layer][];
        for (int i = 0; i < layer; i++) {
            data[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                data[i][j] = myScanner.nextInt();
            }
        }
        /*-----状态转移-----*/
        int[][] f = new int[layer][];
        // 状态初始化
        f[0] = new int[1];
        f[0][0] = data[0][0];
        // 状态转移
        int max = Integer.MIN_VALUE;
        // 通过当前节点获取当前节点可以走过的后继节点
        // 每一个节点的左下方节点肯定存在，右下方节点可能不存在，需要进行数组越界判断
        for (int i = 0; i < layer - 1; i++) {
            f[i + 1] = new int[i + 2];
            Arrays.fill(f[i + 1], -100000);
            for (int j = 0; j <= i; j++) {
                f[i + 1][j] = Math.max(f[i + 1][j], f[i][j] + data[i + 1][j]);
                f[i + 1][j + 1] = Math.max(f[i + 1][j + 1], f[i][j] + data[i + 1][j + 1]);
            }
        }
        // 因为可以存在负数，所以三角形数据中只有最后一行的最大值才能是最大值
        for (int i = 0; i < layer; i++) {
            max = Math.max(max, f[layer - 1][i]);
        }

        System.out.print(max);
    }
}
